import java.util.*;

public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().permuteUnique(new int[]{1,1,2}));
    }
}

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        Deque<Integer> cur = new ArrayDeque<>(nums.length);
        List<List<Integer>> ans = new ArrayList<>();
        backtracking(nums, cur, ans);
        return ans;
    }

    void backtracking(int[] ordered, Deque<Integer> cur, List<List<Integer>> ans) {
        if (cur.size() == ordered.length) {
            ans.add(new ArrayList<>(cur));
            return;
        }

        for (int i = 0; i < ordered.length; i++) {
            while (i < ordered.length && i > 0 && ordered[i] == ordered[i - 1]) {
                i++;
            }
            while (i < ordered.length && ordered[i] == Integer.MAX_VALUE) {
                i++;
            }
            if (i == ordered.length) {
                break;
            }
            cur.offerLast(ordered[i]);
            ordered[i] = Integer.MAX_VALUE;
            backtracking(ordered, cur, ans);
            ordered[i] = cur.pollLast();
        }

    }

}